#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/22 16:00
# ===========================================
#       题目名称： 25. K 个一组翻转链表
#       题目地址： https://leetcode.cn/problems/reverse-nodes-in-k-group/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from utils import StringUtils
import copy


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
        实现思路：
            定义一个临时节点用于存放 边遍历 边存放
    """

    def reverseKGroup(self, head, k):
        res = None  # 返回值
        while head:
            # 获取当前反转的列表数据
            cur_k = k - 1  # 当前k
            temp_cur_node = cur_node = copy.deepcopy(head)  # 当前节点
            while cur_k > 0:
                if not temp_cur_node:
                    break
                temp_cur_node = temp_cur_node.next
                head = head.next
                if head:
                    cur_k -= 1
            if head and head.next:
                head = head.next
            else:
                head = None
            if temp_cur_node and temp_cur_node.next:
                temp_cur_node.next = None
            # 对当前的数据进行判断
            new_node = None
            while cur_node:
                if new_node:
                    if cur_k == 0:  # 刚好可以进行反转
                        new_node = ListNode(cur_node.val, new_node)
                    else:
                        temp_new_node = new_node
                        while temp_new_node and temp_new_node.next:
                            temp_new_node = temp_new_node.next
                        temp_new_node.next = ListNode(cur_node.val)
                else:
                    new_node = ListNode(cur_node.val)
                cur_node = cur_node.next
            if res:
                temp_res = res
                while temp_res and temp_res.next:
                    temp_res = temp_res.next
                temp_res.next = new_node
            else:
                res = new_node
        return res


if __name__ == '__main__':
    s = Solution()
    # [1,2,3,4,5]
    print(StringUtils.to_string(s.reverseKGroup(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), k=9)))
    # [2,1,4,3,5]
    print(StringUtils.to_string(s.reverseKGroup(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), k=2)))
    # [3,2,1,4,5]
    print(StringUtils.to_string(s.reverseKGroup(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), k=3)))
    # [1,2,3,4,5]
    print(StringUtils.to_string(s.reverseKGroup(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), k=1)))
